package com.example.algorithm.backtrcaking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/8/23
 * ip号码
 */
public class IPNum {

    List<String> list=new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        if(s.length()>12){
            return list;
        }
        backTracking(s,0,0);
        return list;
    }

    private void backTracking(String s, int satrtIndex, int pointNum) {

        if(pointNum==3){
            if(isValid(s,satrtIndex,s.length()-1)){
                list.add(s);
            }
            return;
        }
        for(int i=satrtIndex;i<s.length();i++)
        {
            if(isValid(s,satrtIndex,i)){
                s=s.substring(0,i+1)+"."+s.substring(i+1);
                pointNum++;
                backTracking(s, i+2, pointNum);
                pointNum--;
                s=s.substring(0,i+1)+s.substring(i+2);
            }else {
                break;
            }
        }
    }

    private boolean isValid(String s,int startIndex, int endIndex) {

        if(startIndex>endIndex){
            return false;
        }
        //零只能开头
        if(s.charAt(startIndex)=='0'&&startIndex!=endIndex)
        {
            return false;
        }
        int num=0;
        for(int i=startIndex;i<=endIndex;i++)
        {
            if(s.charAt(i)<'0'||s.charAt(i)>'9')
            {
                return false;
            }
            num=num*10+(s.charAt(i)-'0');
            if(num>255){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        IPNum ipNum = new IPNum();
        List<String> list = ipNum.restoreIpAddresses("25525511135");
        list.stream().forEach(System.out::println);
    }
}
